// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 多精度十进制数。
// 仅用于浮点格式；不是通用的。
// 只有赋值和（二进制）左/右移位操作。
// 可以精确地进行多精度十进制中的二进制浮点运算
// 因为2除以10；无法在多精度二进制中精确执行十进制浮点
// 运算。

package strconv

type decimal struct {
	d     [800]byte // 数字，大端表示
	nd    int       // 使用的位数
	dp    int       // 小数点
	neg   bool      // 负标志
	trunc bool      // 丢弃d[：nd]以外的非零数字
}

func (a *decimal) String() string {
	n := 10 + a.nd
	if a.dp > 0 {
		n += a.dp
	}
	if a.dp < 0 {
		n += -a.dp
	}

	buf := make([]byte, n)
	w := 0
	switch {
	case a.nd == 0:
		return "0"

	case a.dp <= 0:
		// 零填充小数点和数字之间的空格
		buf[w] = '0'
		w++
		buf[w] = '.'
		w++
		w += digitZero(buf[w : w+-a.dp])
		w += copy(buf[w:], a.d[0:a.nd])

	case a.dp < a.nd:
		// 数字中间的小数点
		w += copy(buf[w:], a.d[0:a.dp])
		buf[w] = '.'
		w++
		w += copy(buf[w:], a.d[a.dp:a.nd])

	default:
		// 零填充数字和小数点之间的空格
		w += copy(buf[w:], a.d[0:a.nd])
		w += digitZero(buf[w : w+a.dp-a.nd])
	}
	return string(buf[0:w])
}

func digitZero(dst []byte) int {
	for i := range dst {
		dst[i] = '0'
	}
	return len(dst)
}

// 从数字中删除尾随的零。
// （它们没有意义；小数点跟踪
// 与位数无关。）
func trim(a *decimal) {
	for a.nd > 0 && a.d[a.nd-1] == '0' {
		a.nd--
	}
	if a.nd == 0 {
		a.dp = 0
	}
}

// 将v分配给a。
func (a *decimal) Assign(v uint64) {
	var buf [24]byte

	// 用buf写入反向十进制。
	n := 0
	for v > 0 {
		v1 := v / 10
		v -= 10 * v1
		buf[n] = byte(v + '0')
		n++
		v = v1
	}

	// 再次反转以产生公元前向小数。
	a.nd = 0
	for n--; n >= 0; n-- {
		a.d[a.nd] = buf[n]
		a.nd++
	}
	a.dp = a.nd
	trim(a)
}

// 一次可以进行的最大移位，不会溢出。
// 单元有32位或64位，我们必须能够容纳9位。
const uintSize = 32 << (^uint(0) >> 63)
const maxShift = uintSize - 4

// 二进制右移（/2）k位。k<=maxShift以避免溢出。
func rightShift(a *decimal, k uint) {
	r := 0 // 读取指针
	w := 0 // 写入指针

	// 拾取足够的前导数字以覆盖第一个移位。
	var n uint
	for ; n>>k == 0; r++ {
		if r >= a.nd {
			if n == 0 {
				// a==0；不应该到这里，但无论如何要处理好。
				a.nd = 0
				return
			}
			for n>>k == 0 {
				n = n * 10
				r++
			}
			break
		}
		c := uint(a.d[r])
		n = n*10 + c - '0'
	}
	a.dp -= r - 1

	var mask uint = (1 << k) - 1

	// 拿起一个数字，放下一个数字。
	for ; r < a.nd; r++ {
		c := uint(a.d[r])
		dig := n >> k
		n &= mask
		a.d[w] = byte(dig + '0')
		w++
		n = n*10 + c - '0'
	}

	// 请输入额外的数字。
	for n > 0 {
		dig := n >> k
		n &= mask
		if w < len(a.d) {
			a.d[w] = byte(dig + '0')
			w++
		} else if dig > 0 {
			a.trunc = true
		}
		n = n * 10
	}

	a.nd = w
	trim(a)
}

// 左移位备忘单：根据移位计数索引的表，给出了
// 该移位将引入的新位数。
// 
// 例如，leftcheats[4]={2，“625”}。也就是说，如果我们用4移位（乘以16），当字符串前缀为“625”到“999”时，它将加上2位
// 而当字符串前缀为“000”到“624”时，它将少加一位
// 。
// 
// 这个把戏的功劳归于肯。

type leftCheat struct {
	delta  int    // 新位数
	cutoff string // 如果原始<a，则减去一位数。
}

var leftcheats = []leftCheat{
	// 1/2^i=5^i的前导数字。
	// 5^23不是一个精确的64位浮点数，
	// 因此必须使用bc进行数学运算。
	// 增加到60，使其足够大，可用于32位和64位平台。
	/*
		seq 60 | sed 's/^/5^/' | bc |
		awk 'BEGIN{ print "\t{ 0, \"\" }," }
		{
			log2 = log(2)/log(10)
			printf("\t{ %d, \"%s\" },\t// /*%d\n",193
				int(log2*NR+1), $0, 2**NR)
		}'
	*/
	{0, ""},
	{5, "6103515625"},                                  // /*16384 
	{5, "30517578125"},                                 // /*32768 
	{5, "152587890625"},                                // /*65536 
	{6, "762939453125"},                                // /*131072 
	{6, "3814697265625"},                               // /*262144 
	{6, "19073486328125"},                              // /*524288 
	{7, "95367431640625"},                              // /*1048576 
	{7, "476837158203125"},                             // /*2097152 
	{7, "2384185791015625"},                            // /*4194304 
	{8, "298023223876953125"},                          // /*33554432 
	{8, "1490116119384765625"},                         // /*67108864 
	{9, "7450580596923828125"},                         // /*134217728 
	{9, "37252902984619140625"},                        // /*268435456 
	{9, "186264514923095703125"},                       // /*536870912 
	{10, "4656612873077392578125"},                     // /*2147483648 
	{11, "2910383045673370361328125"},                  // /*34359738368 
	{11, "14551915228366851806640625"},                 // /*68719476736 
	{12, "72759576141834259033203125"},                 // /*137438953472 
	{12, "363797880709171295166015625"},                // /*2748779006944 
	{12, "1818989403545856475830078125"},               // /*549755813888 
	{14, "5684341886080801486968994140625"},            // /*17592186044416 
	{14, "28421709430404007434844970703125"},           // /*35184372088832 
	{14, "142108547152020037174224853515625"},          // /*70368744177664 
	{15, "710542735760100185871124267578125"},          // /*140737488355328 
	{16, "11102230246251565404236316680908203125"},     // /*9007199254740992 
	{17, "55511151231257827021181583404541015625"},     // /*18014398509481984 
	{18, "6938893903907228377647697925567626953125"},   // /*1441151880755872 
}

// b的前导前缀是否在词典中小于s？
func prefixIsLessThan(b []byte, s string) bool {
	for i := 0; i < len(s); i++ {
		if i >= len(b) {
			return true
		}
		if b[i] != s[i] {
			return b[i] < s[i]
		}
	}
	return false
}

// 二进制左移（*2）k位。k<=maxShift以避免溢出。
func leftShift(a *decimal, k uint) {
	delta := leftcheats[k].delta
	if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {
		delta--
	}

	r := a.nd         // 读取索引
	w := a.nd + delta // 写入索引

	// 拿起一个数字，放下一个数字。
	var n uint
	for r--; r >= 0; r-- {
		n += (uint(a.d[r]) - '0') << k
		quo := n / 10
		rem := n - 10*quo
		w--
		if w < len(a.d) {
			a.d[w] = byte(rem + '0')
		} else if rem != 0 {
			a.trunc = true
		}
		n = quo
	}

	// 请输入额外的数字。
	for n > 0 {
		quo := n / 10
		rem := n - 10*quo
		w--
		if w < len(a.d) {
			a.d[w] = byte(rem + '0')
		} else if rem != 0 {
			a.trunc = true
		}
		n = quo
	}

	a.nd += delta
	if a.nd >= len(a.d) {
		a.nd = len(a.d)
	}
	a.dp += delta
	trim(a)
}

// 二进制左移（k>0）或右移（k<0）。
func (a *decimal) Shift(k int) {
	switch {
	case a.nd == 0:
		// 无事可做：a==0 
	case k > 0:
		for k > maxShift {
			leftShift(a, maxShift)
			k -= maxShift
		}
		leftShift(a, uint(k))
	case k < 0:
		for k < -maxShift {
			rightShift(a, maxShift)
			k += maxShift
		}
		rightShift(a, uint(-k))
	}
}

// 如果我们在第n位切掉a，我们应该四舍五入吗？
func shouldRoundUp(a *decimal, nd int) bool {
	if nd < 0 || nd >= a.nd {
		return false
	}
	if a.d[nd] == '5' && nd+1 == a.nd { // 正好是一半-甚至是
		// 如果我们截断了，比记录的要高一点-总是把
		if a.trunc {
			return true
		}
		return nd > 0 && (a.d[nd-1]-'0')%2 != 0
	}
	// 不一半-数字告诉所有
	return a.d[nd] >= '5'
}

// 从a到nd数字（或更少）。
// 如果nd为零，则表示我们正在将
// 四舍五入到数字的左侧，如
// 0.09->0.1。
func (a *decimal) Round(nd int) {
	if nd < 0 || nd >= a.nd {
		return
	}
	if shouldRoundUp(a, nd) {
		a.RoundUp(nd)
	} else {
		a.RoundDown(nd)
	}
}

// 将a四舍五入到第nd位（或更少）。
func (a *decimal) RoundDown(nd int) {
	if nd < 0 || nd >= a.nd {
		return
	}
	a.nd = nd
	trim(a)
}

// 将a四舍五入到第nd位（或更少）。
func (a *decimal) RoundUp(nd int) {
	if nd < 0 || nd >= a.nd {
		return
	}

	// 汇总
	for i := nd - 1; i >= 0; i-- {
		c := a.d[i]
		if c < '9' { // 此数字后可停止
			a.d[i]++
			a.nd = i + 1
			return
		}
	}

	// 数字均为9。
	// 更改为带调整小数点的单个1。
	a.d[0] = '1'
	a.nd = 1
	a.dp++
}

// 提取整数部分，适当四舍五入。
// 不保证溢出。
func (a *decimal) RoundedInteger() uint64 {
	if a.dp > 20 {
		return 0xFFFFFFFFFFFFFFFF
	}
	var i int
	n := uint64(0)
	for i = 0; i < a.dp && i < a.nd; i++ {
		n = n*10 + uint64(a.d[i]-'0')
	}
	for ; i < a.dp; i++ {
		n *= 10
	}
	if shouldRoundUp(a, a.dp) {
		n++
	}
	return n
}
